#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/20 10:44
# @USER    : Shengji He
# @File    : MergeIntervals.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        """
        Given a collection of intervals, merge all overlapping intervals.

        Example 1:
            Input: [[1,3],[2,6],[8,10],[15,18]]

            Output: [[1,6],[8,10],[15,18]]

            Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
        Example 2:
            Input: [[1,4],[4,5]]

            Output: [[1,5]]

            Explanation: Intervals [1,4] and [4,5] are considered overlapping.
        NOTE: input types have been changed on April 15, 2019. Please reset to default code definition
        to get new method signature.

        :param intervals:
        :return:
        """

        # if len(intervals) < 2:
        #     return intervals
        # ans = []
        # intervals = sorted(intervals)
        # for i in range(0, len(intervals)):
        #     if i == 0:
        #         ls = intervals[i][0]
        #         rs = intervals[i][1]
        #     else:
        #         if intervals[i][0] > rs:
        #             ans.append([ls, rs])
        #             ls = intervals[i][0]
        #             rs = intervals[i][1]
        #         elif intervals[i][1] > rs:
        #             rs = intervals[i][1]
        #         else:
        #             pass
        #     if i == len(intervals) - 1:
        #         ans.append([ls, rs])
        #
        # return ans
        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            # 如果列表为空，或者当前区间与上一区间不重合，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 否则的话，我们就可以与上一区间进行合并
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged


if __name__ == '__main__':
    S = Solution()
    intervals = [[2, 3], [4, 5], [6, 7], [8, 9], [1, 10]]
    # intervals = [[1, 4], [0, 4]]
    # intervals = [[1, 4], [4, 5]]
    # intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
    print(S.merge(intervals))
    print('done')
